package leetcode;

import java.util.*;

public class Code013_SmallestSubsequence {
    
    public static String smallestSubsequence(String s){
        
        int len = s.length();
        char[] chars = s.toCharArray();
        Deque<Integer> stack = new ArrayDeque<>();
        HashSet<Character> set = new HashSet<>();
        int[] lastIndex = new int[26];
        for(int i = 0; i < len; i++){
            lastIndex[chars[i] - 'a'] = i;
        }
        for(int i = 0; i < len; i++){
            if(set.contains(chars[i])){
                continue;
            }
            while(!stack.isEmpty() &&
                    chars[stack.peek()] > chars[i] &&
                    i-1 < lastIndex[chars[stack.peek()] - 'a']){
                int cur = stack.pop();
                set.remove(chars[cur]);
            }

            stack.push(i);
            set.add(chars[i]);

        }
        StringBuilder res = new StringBuilder();
        for (int cur : stack) {
            res.append(chars[cur]);
        }

        return res.reverse().toString();
    }

    public static void main(String[] args) {
        String s = "abba";
        String s2 = "bcbcababa";
        String s3 = "cbacdcbc";
        String res = smallestSubsequence(s3);
        System.out.println(res);
    }
}
